package binaryTree;

public class D230722 {
    // 序列化二叉树
    // 按前序遍历的方式序列化和反序列化
    private int index = 0;
    public String Serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        intervalSerialize(builder, root);
        return builder.toString();
    }
    private void intervalSerialize(StringBuilder builder, TreeNode root) {
        // ！作为节点的分隔符    15!#!123!
        // 前序遍历进行序列化，节点用 # 表示，根左右
        if (root == null) {
            builder.append('#').append('!');
            return;
        }
        builder.append(root.val).append('!');
        intervalSerialize(builder, root.left);
        intervalSerialize(builder, root.right);
    }
    public TreeNode Deserialize(String str) {
        if (str == null || str.isEmpty()) {
            return null;
        }
        // 用 ！分割节点，数字中每个元素代表一个节点
        String[] words = str.split("!");
        return internalDeserialize(words);
    }
    private TreeNode internalDeserialize(String[] words) {
        // 前序遍历反序列化
        if (index == words.length) {
            return null;
        }
        if ("#".equals(words[index])) {
            // 空节点，返回 null
            return null;
        }
        // 不是空节点，将 "123" 转为 123
        TreeNode root = new TreeNode(Integer.parseInt(words[index]));
        index++;
        root.left = internalDeserialize(words);
        index++;
        root.right = internalDeserialize(words);
        return root;
    }
}
